// Copyright 2012 The go-algs Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package bst implements functions for the creation and manipulation of binary
// search trees.  For more documentation on this data structure please see
// chapter 12 of CLRS 2nd edition.
package bst

// binary search tree from CLRS 12.
type BST struct {
	P *BST // Parent
	L *BST // Left child
	R *BST // Right child
	K int  // Key
}

// Insert a node into an existing BST.  Note that a node in this case could also
// be a tree with one or more children.
func (b *BST) Insert(n *BST) {
	if b.K > n.K {
		if b.L == nil {
			b.L = n
			n.P = b
			return
		}
		b.L.Insert(n)
		return
	}
	if b.R == nil {
		b.R = n
		n.P = b
		return
	}
	b.R.Insert(n)
}

// Search the BST for a node with the given key and return a pointer to that
// node.
func (b *BST) Search(k int) *BST {
	if b.K == k {
		return b
	}
	if b.K > k {
		if b.L != nil {
			return b.L.Search(k)
		}
		return nil
	}
	if b.R != nil {
		return b.R.Search(k)
	}
	return nil
}

// Successor finds and returns the BST node that is the next largest or equal
// in key value.
func (b *BST) Successor() *BST {
	if b.R != nil {
		// The minimum value of the right sub-tree is the smallest value in the
		// tree that is at least the value of this node.
		return b.R.Min()
	}
	// This node does not have a right sub-tree so we will need to walk up the
	// tree to find the first left branch leading to this node.
	x := b
	y := b.P
	for {
		// test for root or left child
		if y == nil || x != y.R {
			// if we are the root node or the left child then the parent (y) is
			// b's successor.
			return y
		}
		// otherwise keep walking
		x = y
		y = y.P
	}
	panic("unreachable")
}

// Min returns a pointer to a node that has the least value in the tree.
func (b *BST) Min() *BST {
	if b.L != nil {
		return b.L.Min()
	}
	return b
}

// Max returns a pointer to a node that has the greatest value in the tree.
func (b *BST) Max() *BST {
	if b.R != nil {
		return b.R.Max()
	}
	return b
}

// Walk returns an array of sorted integers representing the values in the BST.
// This is an in-order walk of the tree.
func (b *BST) Walk() []int {
	var r []int
	if b.L != nil {
		r = b.L.Walk()
	}
	r = append(r, b.K)
	if b.R != nil {
		r = append(r, b.R.Walk()...)
	}
	return r
}

// Delete removes the node from the tree.  
func (b *BST) Delete(n *BST) {
	y := n
	if n.L != nil && n.R != nil {
		y = n.Successor()
	}
	x := y.L
	if x == nil {
		x = y.R
	}
	if x != nil {
		x.P = y.P
	}
	if y.P != nil {
		if y == y.P.L {
			y.P.L = x
		} else {
			y.P.R = x
		}
	}
	if y != n {
		n.K = y.K
		return
	}
}
